package com.lx.algorithm.temp;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-10-28 22:01:24
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-10-28     张李鑫                     1.0         1.0 Version
 */
public class HorseJump {
    /**
     * 请同学们自行搜索或者想象一个象棋的棋盘，
     * 然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置
     * 那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域
     * 给你三个 参数 x，y，k
     * 返回“马”从(0,0)位置出发，必须走k步
     * 最后落在(x,y)上的方法数有多少种?
     */


    public static int jump(int x, int y, int k) {
        return jump(0, 0, x, y, k);
    }

    public static int jump(int a, int b, int x, int y, int k) {
        if (k == 0) {
            return (a == x && b == y) ? 1 : 0;
        }
        if (a < 0 || a > 8 || b < 0 || b > 9) {
            return 0;
        }
        int way = 0;
        way += jump(a + 1, b + 2, x, y, k - 1);
        way += jump(a + 1, b - 2, x, y, k - 1);
        way += jump(a + 2, b + 1, x, y, k - 1);
        way += jump(a + 2, b - 1, x, y, k - 1);
        way += jump(a - 1, b + 2, x, y, k - 1);
        way += jump(a - 1, b - 2, x, y, k - 1);
        way += jump(a - 2, b + 1, x, y, k - 1);
        way += jump(a - 2, b - 1, x, y, k - 1);
        return way;
    }

    public static int dp(int x, int y, int k) {
        int[][][] dp = new int[10][9][k + 1];
        dp[x][y][0]=1;
        for (int i = 1; i <= k; i++) {
            for (int i1 = 0; i1 < 10; i1++) {
                for (int i2 = 0; i2 < 9; i2++) {
                    int way=0;
                    way += pick(i2 - 2, i1 + 1, dp, i - 1);
                    way += pick(i2 - 1, i1 + 2, dp, i - 1);
                    way += pick(i2 + 1, i1 + 2, dp,i-1);
                    way += pick(i2 + 2, i1 + 1, dp, i- 1);
                    way += pick(i2 + 2, i1 - 1, dp, i - 1);
                    way += pick(i2 + 1, i1 - 2, dp, i - 1);
                    way += pick(i2 - 1, i1 - 2, dp, i - 1);
                    way += pick(i2 - 2, i1 - 1, dp, i - 1);
                    dp[i1][i2][i]=way;
                }
            }
        }
        return dp[0][0][k];
    }

    public static int pick(int a,int b,int [][][]dp,int k){
        if (a < 0 || a > 8 || b < 0 || b >9) {
            return 0;
        }
        return dp[b][a][k];
    }

    public static void main(String[] args) {
        int x = 7;
        int y = 7;
        int step = 10;
        System.out.println(jump(x, y, step));
        System.out.println(dp(x, y, step));

    }
}